import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * User: 花海
 * Date: 2022-10-18
 * Time: 21:34
 */
public class Sort {
    private  static  void swap(Integer a,Integer b){
        Integer temp=a;
        a=b;
        b=temp;


    }
    public static void insertSort(int[] array){
        //插入排序
        for (int i = 1; i < array.length ; i++) {
            int j=i-1;
            int temp=array[i];//把一个元素拿出来

            while(j>=0){


                if(array[j]>temp){
                    array[j+1] = array[j];
                    j--;//如果找到的元素比temp大那么往后放

                }else{
                    array[j+1]=temp;
                    break;//找到的元素比temp小那么temp本轮现被放在这里 break出循环寻找下一个树
                }
            }
            array[j+1]=temp;


        }
    }
    //思想:选出n个中最小的放在0位置再从n-1中选出最小的放到n1位置
public static void selectSort(int[] array) {
    int len = array.length;
    int mid = len / 2;
    for (int i = 0; i < mid; i++) {
        int minindex = 0;
        int maxindex = 0;
        //i用来控制插入位置
        int min = 100000;
        int max = 0;
        for (int j = i; j < array.length - i; j++) {

            if (array[j] < min) {
                minindex = j;
                min = array[j];
            }


            if (array[j] > max) {
                maxindex = j;
                max = array[j];
            }


        }
        //swap(array[i],array[minindex]);
        int temp = array[i];
        array[i] = array[minindex];
        array[minindex] = temp;
        // swap(array[len-1],array[maxindex]);
        int temp1 = array[len - 1];
        array[len - 1] = array[maxindex];
        array[maxindex] = temp1;
        len--;


    }
}
    // 冒泡排序
public static void bubbleSort(int[]  array){
        for (int i =0; i < array.length; i++) {
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }

            }

        }
    }
    //堆排序

public static void heapSort(int[] array){

        // write code  here
    PriorityQueue<Integer>pr=new PriorityQueue<>(new Comparator<Integer>(){
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }

    });
    for (int i = 0; i < array.length; i++) {
        pr.add(array[i]);

    }

    for (int i = 0; i < array.length ; i++) {
       array[i]= pr.poll();
    }
    }

// 快速
public static void quickSort(int[] array,int left,int right){
        if(left>right){
            return;
        }
        int mid= por(array,left, right);
        quickSort(array,left,mid-1);
        quickSort(array,mid+1, array.length-1);




    // write code  here
    }
    private static int por(int []array,int left,int right){

        int temp=array[left];
        int tempindex=left;
        int rightindex=right;
        while(left<right) {
            while (left < right&&array[right]>=temp){
                right--;
            }
            while (left < right && array[left] <=temp) {
                left++;

            }



                int te=array[left];
                array[left]=array[right];
                array[right]=te;



        }

        int teq= array[tempindex];
        array[tempindex]=array[left];
        array[left]=teq;
        return left;



    }
/*    Comparable 和 Comparator的区别是：

    实现Comparable接口的类，该类的对象可以直接进行比较，也就是说：Student接口实现了Comparable接口后，Student的对象之间可以直接进行比较了，那sort就可以直接排序，即Arrays.sort(students);

    public class Student implements Comparable<Student> {public String name;
        public int score;
        public Student(){
        }
        public Student(String name, int score){
            this.name = name;
            this.score = score;
        }
        @Override
        public int compareTo(Student o) {
            return o.score - score;
        }
        @Override
        public String toString() {
            return "[" + name + "," + score + "]";
        }
        public static void main(String[] args) {
            Student[] students = new Student[3];
            students[0] = new Student("张三", 90);
            students[1] = new Student("李四", 100);
            students[2] = new Student("王五", 80);
            Arrays.sort(students);
            System.out.println(students[0]);
            System.out.println(students[1]);
            System.out.println(students[2]);
        }
    }
    实现Comparator接口的类，该类的对象不能直接比较，一般是作为比较器提供给其他方法使用的，也就是说：Student如果实现了Comparator接口后，Student并不能进行比较,r如果要比较，必须让借助Student中compare方法才可以比较

Arrays.sort(students, new Student());

    public class Student implements Comparator<Student> {public String name;
        public int score;
        public Student(){
        }
        public Student(String name, int score){
            this.name = name;
            this.score = score;
        }
        @Override
        public int compare(Student o1, Student o2) {
            return o2.score - o1.score;
        }
        @Override
        public String toString() {
            return "[" + name + "," + score + "]";
        }
        public static void main(String[] args) {
            Student[] students = new Student[3];
            students[0] = new Student("张三", 90);
            students[1] = new Student("李四", 100);
            students[2] = new Student("王五", 80);
            Arrays.sort(students, new Student());
            System.out.println(students[0]);
            System.out.println(students[1]);
            System.out.println(students[2]);
        }
    }
    虽然从本质上来说，都可以对Student数组进行升序排序，但是更合理的方式应该是选择B*/


    public static void main(String[] args) {
        int[] arr=new int[]{1,2,9,4,6,3};
        //insertSort(arr);

        //selectSort(arr);
        //bubbleSort(arr);
        //heapSort(arr);
        System.out.println("fbauisefgusjaf");
        quickSort(arr,0, arr.length-1);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);

        }



    }
}
